package com.cqs.leetcode;

import java.util.Stack;

/**
 * Author:li
 * <p>
 * create date: 18-6-3 00:43
 */
public class ReverseNodesInKGroup {


    private boolean updated = false;
    private ListNode head = null;


    private class ListHelper {
        ListNode head;
        ListNode tail;
    }

    //8ms
    public ListNode reverseKGroup(ListNode head, final int k) {
        if (k == 1) return head;
        this.head = head;
        int count = 0;
        ListNode sp = head;//当前子链表
        ListNode tail = null;//当前子链表
        while (head != null) {
            //生成一个新的子链表
            if (++count % k == 0) {
                ListNode next = head.next;//记录下一个元素
                //生成子链表
                head.next = null;
                ListHelper helper = reverse(sp);
                //更新sp
                sp = next;
                //更新head
                head = next;
                if (tail == null) {
                    tail = helper.tail;
                } else {
                    tail.next = helper.head;
                    tail = helper.tail;
                }
            } else {
                head = head.next;
            }
        }
        if (tail != null)
            tail.next = sp;
        return this.head;
    }

    /**
     * 反转链表
     *
     * @param head
     * @return 返回链表的头和尾
     */
    private ListHelper reverse(ListNode head) {
        ListHelper helper = new ListHelper();
        ListNode pre = null, next;
        ListNode tail = head;
        while (head != null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        if (!updated) {
            updated = true;
            this.head = pre;
        }
        helper.head = pre;
        helper.tail = tail;
        return helper;
    }

    //17ms  beat 3.3%
    public ListNode reverseKGroup2(ListNode head, int k) {
        ListNode node = head, preLast = null;
        boolean newHead = false;
        Stack<ListNode> stack = new Stack<>();
        while (node != null) {
            stack.push(node);
            node = node.next;
            if (stack.size() == k) {
                ListNode pop = null;
                while (!stack.empty()) {
                    if (!newHead) {//新队首元素
                        head = stack.peek();
                        newHead = true;//产生新的头元素
                    }
                    if (stack.size() == k) {
                        if (preLast != null) {
                            preLast.next = stack.peek();
                        }
                    }
                    pop = stack.pop();
                    pop.next = stack.size() == 0 ? node : stack.peek();
                }
                preLast = pop;
                System.out.println(stack.empty() + "\t" + node);
            }
        }
        return head;
    }


    //leetcode 6ms
    public ListNode reverseKGroup3(ListNode head, int k) {
        ListNode curr = head;
        int count = 0;
        while (curr != null && count != k) { // find the k+1 node
            curr = curr.next;
            count++;
        }
        if (count == k) { // if k+1 node is found
            curr = reverseKGroup3(curr, k); // reverse list with k+1 node as head
            // head - head-pointer to direct part,
            // curr - head-pointer to reversed part;
            while (count-- > 0) { // reverse current k-group:
                ListNode tmp = head.next; // tmp - next head in direct part
                head.next = curr; // preappending "direct" head to the reversed list
                curr = head; // move head of reversed part to a new node
                head = tmp; // move "direct" head to the next node in direct part
            }
            head = curr;
        }
        return head;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int k = 2;
        ListNode head = ListNode.build(nums);
        System.out.println(head);
        ReverseNodesInKGroup r = new ReverseNodesInKGroup();
        ListNode listNode = r.reverseKGroup(head, k);
        System.out.println(listNode);
    }


}
